﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.Intrinsics.Arm;
using System.Text;
using System.Threading.Tasks;


//152. 乘积最大子数组
//给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组
//（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
//看到题目想一个暴力解法，双指针i，j遍历两遍，记录所有的乘积
//但是这样导致很多乘积重复计算了，所以 转为动态规划，前面算过的直接转移过来结果
public class Solution152
{
    public int MaxProduct2(int[] nums)//动态规划加双指针，两次遍历复杂度有点大
    {

        int len = nums.Length;

        int[][] dp=new int[len][];
        for (int i = 0; i < len; i++)
        {
            dp[i]=new int[len];
        }
        int max = int.MinValue;
        dp[0][0] = nums[0];
        for (int i =0; i < len; i++)
        {
            dp[i][i] = nums[i];//第一个数字的乘积初始化为nums，而不是0
            for (int j= i+1; j < len;j++)
                
            {
                //以i开头，以j结尾的数组的乘积
                
                    dp[i][j] = dp[i][j - 1] * nums[j];
              
              
                max=Math.Max(max, dp[i][j]);
            }
            max = Math.Max(max, dp[i][i]);

        }
        

        return max;

    }

    public int MaxProduct(int[] nums)//动态规划，只和前一个状态有关
    {
        int len = nums.Length;

        int[] min = new int[len];
        int[] max = new int[len];

        min[0] = nums[0];
        max[0] = nums[0];
        for (int i = 1; i < len; i++)
        {
            max[i] = Math.Max(min[i - 1] * nums[i], Math.Max(max[i - 1] * nums[i], nums[i]));
            min[i] = Math.Min(min[i - 1] * nums[i], Math.Min(max[i - 1] * nums[i], nums[i]));
        
        }
        int res = max[0];
        for (int i = 1; i < len; i++)
        {
           res= Math.Max(res, max[i]);  

        }
        return res;
    }
    }

    class Program152
{

    static void Main152(string[] args)
    {
        Solution152 solution = new Solution152();

        int[] nums = [-2];
      int res=  solution.MaxProduct(nums);
        Console.WriteLine(res);
    }
}